19 задание

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу любое количество камней от одного до количества камней в этой куче. Изменять количество камней в большей куче не разрешается. Если кучи содержат равное количество камней, добавлять камни можно в любую из них. Пусть, например, в начале игры в первой куче 3 камня, а во второй — 5 камней, будем обозначать такую позицию (3, 5). Петя первым ходом должен добавить в первую кучу от 1 до 3 камней, он может получить позиции (4, 5), (5, 5) и (6, 5). Если Петя создаёт позицию (4, 5), то Ваня своим ходом может добавить от 1 до 4 камней в первую кучу, а если Петя создаёт позицию (6, 5), то Ваня может добавить от 1 до 5 камней во вторую кучу, так как теперь она стала меньшей. В позиции (5, 5) Ваня может добавить от 1 до 5 камней в любую кучу.

Игра завершается, когда общее количество камней в кучах становится более 45. Победителем считается игрок, сделавший последний ход, то есть первым получивший 46 или больше камней в двух кучах.

Известно, что Петя смог выиграть первым ходом. Какое наименьшее число камней могло быть суммарно в двух кучах?

20 задание

В игре, описанной в задании 19, в начальный момент в первой куче было 5 камней, а во второй — S камней, 1 ≤ S ≤ 40. Укажите минимальное и максимальное из таких значений S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани.

В ответе запишите сначала минимальное значение, затем максимальное.

21 задание

В игре, описанной в задании 19, в начальный момент в первой куче было 5 камней, а во второй — S камней, 1 ≤ S ≤ 40.

Найдите минимальное из таких значений S, при котором у Вани есть стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.

Добавлено: 10.04.26 19:30

Перейти к решению

def f(m, s1, s2):
    if s1 + s2 > 45:
        return m % 2 == 0
    if m == 0:
        return False
    if s1 <= s2:
        h = [f(m - 1, s1 + i, s2) for i in range(1, s1 + 1)]
    else:
        h = [f(m - 1, s1, s2 + i) for i in range(1, s2 + 1)]
    return any(h) if m % 2 != 0 else all(h)


print("19:",min([s1 + s2 for s1 in range(1, 46) for s2 in range(1, 46) if f(1, s1, s2)]))  # 31
print("20:", [s2 for s2 in range(1, 41) if not f(1, 5, s2) and f(3, 5, s2)])  # 24 33
print("21:", min([s2 for s2 in range(1, 41) if f(4, 5, s2) and not f(2, 5, s2)]))  # 20